package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Fengkai
 * @creat 2023/4/8 0008
 * 输入描述
 * 第一行输入N，N表示有N个小朋友
 * 第二行输入N个小朋友的身高height[i]，都是整数
 * 输出描述
 * 输出N个小朋友的好朋友的位置
 * 示例1   输入输出示例仅供调试，后台判题数据一般不包含示例
 * 输入
 * 2
 * 100 95
 * 输出
 * 0 0
 */
public class FindFriend {
    public static void main (String[] args) {
        for (int i = 0; i < 4000; i++) {
            int size = (int) ((Math.random() * 40000) + 1);
            String s = new String("");
            for (int j = 0; j < size; j++) {
                s += (int) ((Math.random() * 210) + 1) + " ";
            }
            s = s.substring(0, size - 1);
            if (!getFriendIndex(s).equals(hisMethod(s))){
                System.out.println("error");
                System.out.println(getFriendIndex(s));
                System.out.println(hisMethod(s));
            }
        }

    }


    public static String getFriendIndex (String heightstr) {
        String[] heights = heightstr.split(" ");
        ArrayList<String> indexList = new ArrayList<>();
        for (int i = 0; i < heights.length; i++) {
            int index = 0;
            for (int j = i + 1; j < heights.length; j++) {
                if (Integer.parseInt(heights[j]) > Integer.parseInt(heights[i])) {
                    index = j;
                    break;
                }
            }
            indexList.add(index + " ");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (String s : indexList) {
            stringBuilder.append(s);
        }
        return stringBuilder.substring(0, stringBuilder.length() - 1);
    }


    public static String hisMethod (String heightstr) {

        String[] heights = heightstr.split(" ");
        int N = heights.length;
        //单调栈
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int height1 = Integer.parseInt(heights[i]);
            int index = 0;
            for (int j = i; j < N; j++) {
                int height2 = Integer.parseInt(heights[j]);
                if (height2 > height1) {
                    index = j;
                    break;
                }
            }
            list.add(index);
        }

        //输出
        StringBuilder sb = new StringBuilder();
        for (int i : list) {
            sb.append(i).append(" ");
        }
        sb.setLength(sb.length() - 1);
        return sb.toString();
    }
}
